// Copyright 2013 By Jshi. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package sort

import . "sort"

// Find the middle element of |data|.
func pivot(data Interface, lo, hi int) (mi int) {
	i, i1, i2 := lo, lo+1, hi-1
	for {
		for i1 < data.Len() && data.Less(i1, i) {
			i1++
		}
		for i2 >= 0 && data.Less(i, i2) {
			i2--
		}
		if i1 >= i2 {
			data.Swap(i, i2)
			mi = i2
			return
		}
		data.Swap(i1, i2)
	}
}

// Quick sort implement.
func quickSort(data Interface, lo, hi int) {
	if lo < hi {
		mi := pivot(data, lo, hi)
		quickSort(data, lo, mi)
		quickSort(data, mi+1, hi)
	}
}

// Quick sort interface.
func QuickSort(data Interface) {
	quickSort(data, 0, data.Len())
}
